Integer programs defined by two equations with two free integer variables andnonnegative continuous variables have three types of nontrivial facets: split,triangle or quadrilateral inequalities. In this paper, we compare the strengthof these three families of inequalities. In particular we study how well eachfamily approximates the integer hull. We show that, in a well defined sense,triangle inequalities provide a good approximation of the integer hull. Thesame statement holds for quadrilateral inequalities. On the other hand, theapproximation produced by split inequalities may be arbitrarily bad.
展开▼
